
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2300. -- [HAOI2011]防线修建 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2300: [HAOI2011]防线修建</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>512 MB<br><span class=green>Submit: </span>150&nbsp;&nbsp;<span class=green>Solved: </span>66<br>[<a href='submitpage.php?id=2300'>Submit</a>][<a href='problemstatus.php?id=2300'>Status</a>][<a href='bbs.php?id=2300'>Discuss</a>]</center><h2>Description</h2><div class=content><p><!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]--><!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:PunctuationKerning />
<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>
<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>
<w:ValidateAgainstSchemas />
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:Compatibility>
<w:SpaceForUL />
<w:BalanceSingleByteDoubleByteWidth />
<w:DoNotLeaveBackslashAlone />
<w:ULTrailSpace />
<w:DoNotExpandShiftReturn />
<w:AdjustLineHeightInTable />
<w:BreakWrappedTables />
<w:SnapToGridInCell />
<w:WrapTextWithPunct />
<w:UseAsianBreakRules />
<w:DontGrowAutofit />
<w:UseFELayout />
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" LatentStyleCount="156">
</w:LatentStyles>
</xml><![endif]--><!--[if !mso]><object
classid="clsid:38481807-CA0E-42D2-BF39-B33AF135CC4D" id=ieooui></object>
<style>
st1\:*{behavior:url(#ieooui) }
</style>
<![endif]--><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:普通表格;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]--></p>
<p><span style="font-size: 12pt; font-family: 宋体;">近来</span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">A</span><span style="font-size: 12pt; font-family: 宋体;">国和</span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">B</span><span style="font-size: 12pt; font-family: 宋体;">国的矛盾激化，为了预防不测，</span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">A</span><span style="font-size: 12pt; font-family: 宋体;">国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。可是</span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">A</span><span style="font-size: 12pt; font-family: 宋体;">国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于</span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">A</span><span style="font-size: 12pt; font-family: 宋体;">国的经费有限，所以希望你能帮忙完成如下的一个任务：</span></p>
<p class="MsoNormal" style="margin-left: 39pt; text-indent: -18pt;"><span lang="EN-US" style="font-size: 12pt; font-family: Arial;"><span style="">1.<span style="font: 7pt &quot;Times New Roman&quot;;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><span style="font-size: 12pt; font-family: 宋体;">给出你所有的</span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">A</span><span style="font-size: 12pt; font-family: 宋体;">国城市坐标</span></p>
<p class="MsoNormal" style="margin-left: 39pt; text-indent: -18pt;"><span lang="EN-US" style="font-size: 12pt; font-family: Arial;"><span style="">2.<span style="font: 7pt &quot;Times New Roman&quot;;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">A</span><span style="font-size: 12pt; font-family: 宋体;">国上层经过讨论，考虑到经济问题，决定取消对</span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">i</span><span style="font-size: 12pt; font-family: 宋体;">城市的保护，也就是说</span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">i</span><span style="font-size: 12pt; font-family: 宋体;">城市不需要在防线内了</span></p>
<p class="MsoNormal" style="margin-left: 39pt; text-indent: -18pt;"><span lang="EN-US" style="font-size: 12pt; font-family: Arial;"><span style="">3.<span style="font: 7pt &quot;Times New Roman&quot;;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">A</span><span style="font-size: 12pt; font-family: 宋体;">国上层询问对于剩下要保护的城市，修建防线的总经费最少是多少</span></p>
<p class="MsoNormal" style="margin-left: 21pt;"><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">&nbsp;</span></p>
<p class="MsoNormal" style="margin-left: 21pt;"><span style="font-size: 12pt; font-family: 宋体;">你需要对每次询问作出回答。注意单位</span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">1</span><span style="font-size: 12pt; font-family: 宋体;">长度的防线花费为</span><span lang="EN-US" style="font-size: 12pt; font-family: Arial;">1</span><span style="font-size: 12pt; font-family: 宋体;">。</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size: 12pt;">&nbsp;</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size: 12pt;">A</span><span style="font-size: 12pt; font-family: 宋体;">国的地形是这样的，形如下图，</span><span lang="EN-US" style="font-size: 12pt;">x</span><span style="font-size: 12pt; font-family: 宋体;">轴是一条河流，相当于一条天然防线，不需要你再修建</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size: 12pt;">A</span><span style="font-size: 12pt; font-family: 宋体;">国总是有两个城市在河边，一个点是</span><span lang="EN-US" style="font-size: 12pt;">(0,0)</span><span style="font-size: 12pt; font-family: 宋体;">，一个点是</span><span lang="EN-US" style="font-size: 12pt;">(n,0)</span><span style="font-size: 12pt; font-family: 宋体;">，其余所有点的横坐标均大于</span><span lang="EN-US" style="font-size: 12pt;">0</span><span style="font-size: 12pt; font-family: 宋体;">小于</span><span lang="EN-US" style="font-size: 12pt;">n</span><span style="font-size: 12pt; font-family: 宋体;">，纵坐标均大于</span><span lang="EN-US" style="font-size: 12pt;">0</span><span style="font-size: 12pt; font-family: 宋体;">。</span><span lang="EN-US" style="font-size: 12pt;">A</span><span style="font-size: 12pt; font-family: 宋体;">国有一个不在</span><span lang="EN-US" style="font-size: 12pt;">(0,0)</span><span style="font-size: 12pt; font-family: 宋体;">和</span><span lang="EN-US" style="font-size: 12pt;">(n,0)</span><span style="font-size: 12pt; font-family: 宋体;">的首都。</span><span lang="EN-US" style="font-size: 12pt;">(0,0),(n,0)</span><span style="font-size: 12pt; font-family: 宋体;">和首都这三个城市是一定需要保护的。</span></p>
<p class="MsoNormal"><span style="font-size: 12pt; font-family: 宋体;"><img height="255" width="307" src="/JudgeOnline/upload/201105/image/2300_1.jpg" alt="" /></span></p>
<p align="center" class="MsoNormal" style="text-align: center;"><span lang="EN-US" style="font-size: 12pt;"><br />
</span></p>
<p class="MsoNormal" style="text-indent: 24pt;"><span style="font-size: 12pt; font-family: 宋体;">上图中，</span><span lang="EN-US" style="font-size: 12pt;">A,B,C,D,E</span><span style="font-size: 12pt; font-family: 宋体;">点为</span><span lang="EN-US" style="font-size: 12pt;">A</span><span style="font-size: 12pt; font-family: 宋体;">国城市，且目前都要保护，那么修建的防线就会是</span><span lang="EN-US" style="font-size: 12pt;">A-B-C-D</span><span style="font-size: 12pt; font-family: 宋体;">，花费也就是线段</span><span lang="EN-US" style="font-size: 12pt;">AB</span><span style="font-size: 12pt; font-family: 宋体;">的长度</span><span lang="EN-US" style="font-size: 12pt;">+</span><span style="font-size: 12pt; font-family: 宋体;">线段</span><span lang="EN-US" style="font-size: 12pt;">BC</span><span style="font-size: 12pt; font-family: 宋体;">的长度</span><span lang="EN-US" style="font-size: 12pt;">+</span><span style="font-size: 12pt; font-family: 宋体;">线段</span><span lang="EN-US" style="font-size: 12pt;">CD</span><span style="font-size: 12pt; font-family: 宋体;">的长度</span></p>
<p class="MsoNormal" style="text-indent: 24pt;"><span style="font-size: 12pt; font-family: 宋体;">如果，这个时候撤销</span><span lang="EN-US" style="font-size: 12pt;">B</span><span style="font-size: 12pt; font-family: 宋体;">点的保护，那么防线变成下图</span></p>
<p class="MsoNormal" style="text-indent: 24pt;"></p>
<p class="MsoNormal" style="text-indent: 24pt;"><span style="font-size: 12pt; font-family: 宋体;"><img height="271" width="325" src="/JudgeOnline/upload/201105/image/2300_2.jpg" alt="" /></span></p>
<p align="center" class="MsoNormal" style="text-align: center; text-indent: 24pt;"><span lang="EN-US" style="font-size: 12pt;"><br />
</span></p></div><h2>Input</h2><div class=content><p><span style="font-size: 12pt; font-family: 宋体;">第一行，三个整数</span><span lang="EN-US" style="font-size: 12pt;">n,x,y</span><span style="font-size: 12pt; font-family: 宋体;">分别表示河边城市和首都是</span><span lang="EN-US" style="font-size: 12pt;">(0,0)</span><span style="font-size: 12pt; font-family: 宋体;">，</span><span lang="EN-US" style="font-size: 12pt;">(n,0)</span><span style="font-size: 12pt; font-family: 宋体;">，</span><span lang="EN-US" style="font-size: 12pt;">(x,y)</span><span style="font-size: 12pt; font-family: 宋体;">。</span></p>
<p class="MsoNormal"><span style="font-size: 12pt; font-family: 宋体;">第二行，一个整数</span><span lang="EN-US" style="font-size: 12pt;">m</span><span style="font-size: 12pt; font-family: 宋体;">。</span></p>
<p class="MsoNormal"><span style="font-size: 12pt; font-family: 宋体;">接下来</span><span lang="EN-US" style="font-size: 12pt;">m</span><span style="font-size: 12pt; font-family: 宋体;">行，每行两个整数</span><span lang="EN-US" style="font-size: 12pt;">a,b</span><span style="font-size: 12pt; font-family: 宋体;">表示</span><span lang="EN-US" style="font-size: 12pt;">A</span><span style="font-size: 12pt; font-family: 宋体;">国的一个非首都非河边城市的坐标为</span><span lang="EN-US" style="font-size: 12pt;">(a,b)</span><span style="font-size: 12pt; font-family: 宋体;">。</span></p>
<p class="MsoNormal"><span style="font-size: 12pt; font-family: 宋体;">再接下来一个整数</span><span lang="EN-US" style="font-size: 12pt;">q</span><span style="font-size: 12pt; font-family: 宋体;">，表示修改和询问总数。</span></p>
<p class="MsoNormal"><span style="font-size: 12pt; font-family: 宋体;">接下来</span><span lang="EN-US" style="font-size: 12pt;">q</span><span style="font-size: 12pt; font-family: 宋体;">行每行要么形如</span><span lang="EN-US" style="font-size: 12pt;">1 i</span><span style="font-size: 12pt; font-family: 宋体;">，要么形如</span><span lang="EN-US" style="font-size: 12pt;">2</span><span style="font-size: 12pt; font-family: 宋体;">，分别表示撤销第</span><span lang="EN-US" style="font-size: 12pt;">i</span><span style="font-size: 12pt; font-family: 宋体;">个城市的保护和询问。</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size: 12pt;">&nbsp;</span></p>
<p></p></div><h2>Output</h2><div class=content><p><span style="font-size: 12pt; font-family: 宋体;">对于每个询问输出</span><span lang="EN-US" style="font-size: 12pt;">1</span><span style="font-size: 12pt; font-family: 宋体;">行，一个实数</span><span lang="EN-US" style="font-size: 12pt;">v</span><span style="font-size: 12pt; font-family: 宋体;">，表示修建防线的花费，保留两位小数</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size: 12pt;">&nbsp;</span></p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>4 2 1                                <br />
<br />
2                                  <br />
<br />
1 2                               <br />
<br />
3 2                               <br />
<br />
5                                 <br />
<br />
2<br />
<br />
1 1<br />
<br />
2<br />
<br />
1 2<br />
<br />
2<br />
<br />
 <br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata></span></div><h2>HINT</h2>
			<div class=content><p><p><br /><br />
6.47<br /><br />
<br /><br />
5.84<br /><br />
<br /><br />
4.47<br /><br />
<br /><br />
&nbsp;<br /><br />
<br /><br />
数据范围：<br /><br />
<br /><br />
30%的数据m&lt;=1000,q&lt;=1000<br /><br />
<br /><br />
100%的数据m&lt;=100000,q&lt;=200000,n&gt;1<br /><br />
<br /><br />
所有点的坐标范围均在10000以内, 数据保证没有重点</p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=2300'>Submit</a>][<a href='problemstatus.php?id=2300'>Status</a>][<a href='bbs.php?id=2300'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
